Ngay từ thập niên 1950 ông đã nổi tiếng khi là Trưởng Đoàn văn nghệ Vì Dân với thành phần ca nhạc sĩ tên tuổi như Mạnh Phát, Minh Kỳ, Hoài Linh, Thu Hồ, Quách Đàm, Minh Diệu, Khánh Ngọc và các nghệ sĩ danh tiếng như Kim Cương, Vân Hùng, Ba Vân, Bảy Xê, Trần Văn Trạch, diễn viên điện ảnh Trang Thiên Kim,... Ông đã tổ chức và điều khiển các chương trình đại nhạc hội tại Sài Gòn và khắp các tỉnh của Việt Nam Cộng hòa.

Từ năm 1958 ông là Trưởng ban Ca nhạc Tiếng thời gian của Đài Phát thanh Sài Gòn, gồm những danh ca, nhạc sĩ danh tiếng như Lệ Thanh, Hà Thanh, Minh Diệu, Khánh Ngọc, Mạnh Phát, Thu Hồ, Quách Đàm, Anh Ngọc... Năm sau ông là Trưởng ban tổ chức Đại hội thi đua Văn nghệ toàn quốc ở cấp Quốc gia, đã quy tụ trên 40 Đoàn Văn nghệ đại diện cho cả miền Nam cùng tranh giải suốt 15 ngày đêm tại Sài Gòn. Ông cũng từng nhận giải Âm nhạc Quốc gia, một giải thường do bà Trần Lệ Xuân trao tặng.

Ông còn là Giám đốc hãng băng đĩa nhạc Continental và Sơn Ca, cộng tác với những nhạc sĩ tên tuổi như Lê Văn Thiện, Văn Phụng, Nghiêm Phú Phi, Y Vân,... Hai cơ sở của ông cho ra đời nhiều chương trình tân nhạc cũng như cổ nhạc gồm các vở tuồng và cải lương. Ngoài ra ông đã có công phát hiện và đào tạo ca sĩ Thanh Tuyền khi cô còn là nữ sinh Đà Lạt.

Nguyễn Văn Đông là người đã tiên phong thực hiện album riêng cho từng ca sĩ mà trước đó chưa từng ai làm. Ông đã thực hiện loạt băng nhạc Sơn Ca nổi tiếng trong đó có Khánh Ly với băng nhạc Sơn Ca 7, Thái Thanh và Ban Thăng Long – Sơn Ca 10, Lệ Thu – Sơn Ca 9, Phương Dung – Sơn Ca 5 và Sơn Ca 11, Giao Linh – Sơn Ca 6, Sơn Ca – Sơn Ca 8,... và một số album riêng cho Trịnh Công Sơn.

Nhiều sáng tác của ông viết về chủ đề người lính miền Nam thời đó. Nhạc phẩm "Phiên gác đêm xuân" được ông viết vào đêm 30 Tết Nguyên Đán năm 1956 khi gác phiên ở khu 9 Đồng Tháp Mười. "Chiều mưa biên giới" ra đời năm 1956 và nổi tiếng qua tiếng hát của Trần Văn Trạch. "Khúc tình ca hàng hàng lớp lớp" nổi tiếng qua tiếng hát của Hà Thanh nhưng thường bị nhầm với nhạc phẩm "Khúc tình Kinh Kha" của Phạm Duy.

Ông còn có nhiều bút danh khác như Phượng Linh, Phương Hà trên một số nhạc phẩm tình cảm như "Khi đã yêu", "Thầm kín", "Niềm đau dĩ vãng", "Nhớ một chiều xuân"... Với bút danh Đông Phương Tử và Phượng Linh, ông đã viết nhạc nền và đạo diễn cho trên 50 vở tuồng, cải lương nổi tiếng ở Miền Nam trước năm 1975 như Nửa đời hương phấn, Đoạn tuyệt, Tiếng hạc trong trăng, Mưa rừng...

Ca sĩ trình bày thành công: Thanh Tuyền, Hà Thanh, Giao Linh.

Danh sách ca khúc